package main

import (
	"fmt"
)

// 定义一个堆的结构体，包含一个切片和一个大小
type Heap1 struct {
	arr  []int
	size int
}

// 创建一个空的堆
func NewHeap1() *Heap1 {
	return &Heap1{
		arr:  make([]int, 0),
		size: 0,
	}
}

// 返回堆中元素个数
func (h *Heap1) Len() int {
	return h.size
}

// 向堆中添加元素
func (h *Heap1) Push(x int) {
	h.arr = append(h.arr, x)
	h.size++
	h.up(h.size - 1)
}

// 从堆中删除并返回最小元素
func (h *Heap1) Pop() int {
	if h.size == 0 {
		return -1
	}
	x := h.arr[0]
	h.arr[0] = h.arr[h.size-1]
	h.arr = h.arr[:h.size-1]
	h.size--
	h.down(0)
	return x
}

// 上浮操作，维护小顶堆的性质
func (h *Heap1) up(i int) {
	for i > 0 {
		p := (i - 1) / 2         // 父节点的位置
		if h.arr[i] < h.arr[p] { // 如果子节点小于父节点，交换位置
			h.arr[i], h.arr[p] = h.arr[p], h.arr[i]
			i = p // 更新子节点的位置
		} else {
			break // 如果子节点大于等于父节点，退出循环
		}
	}
}

// 下沉操作，维护小顶堆的性质
func (h *Heap1) down(i int) {
	for i < h.size/2 { // 只需要遍历到非叶子节点
		l := i*2 + 1                           // 左孩子的位置
		r := i*2 + 2                           // 右孩子的位置
		min := l                               // 假设左孩子是最小的
		if r < h.size && h.arr[r] < h.arr[l] { // 如果右孩子存在且比左孩子小，更新最小的位置
			min = r
		}
		if h.arr[i] > h.arr[min] { // 如果父节点大于最小的孩子，交换位置
			h.arr[i], h.arr[min] = h.arr[min], h.arr[i]
			i = min // 更新父节点的位置
		} else {
			break // 如果父节点小于等于最小的孩子，退出循环
		}
	}
}

// 堆排序方法，将数组从大到小排列
func Heap1Sort(arr []int) []int {
	n := len(arr)
	if n == 0 {
		return arr
	}
	h := NewHeap1()          // 创建一个空的堆
	for i := 0; i < n; i++ { // 将数组中的元素依次添加到堆中
		h.Push(arr[i])
	}
	for i := n - 1; i >= 0; i-- { // 将堆中的元素依次取出放到数组中
		arr[i] = h.Pop()
	}
	return arr // 返回排序后的数组
}

func main() {
	arr := []int{3, 5, 1, 4, 2} // 定义一个待排序的数组
	fmt.Println("The original array is:", arr)
	arr = Heap1Sort(arr) // 调用堆排序方法对数组进行排序
	fmt.Println("The sorted array is:", arr)
}
